This invention relates to read channel technology for digital data storage systems, and more particularly to a post-processor based upon cyclic code rather than parity code.
Digital data storage systems such as magnetic disks and associated drive apparatus commonly incorporates a so-called read channel that retrieves the accessed data from the analog waveforms provided by the read-head transducer interacting with the magnetic domains on the magnetic disk. As illustrated in FIG. 1a, this technique involves a magnetic disk and head assembly 100 including a stack of several rigid magnetic disks and several magnetic transducers positioned on a movable arm 105 for operable interaction with the magnetic recording surfaces on each disk. These magnetic heads slide or xe2x80x98flyxe2x80x99 in close proximity over the surfaces of the magnetic disks 102 to react to the changes in orientations of magnetic fields of tiny magnetic domains on the disks that represent the stored data. These interactions with magnetic fields produce electrical signals of constantly varying amplitudes that are pre-amplified to produce resulting analog waveforms 106, as shown in FIG. 1b, that are applied to a read-channel integrated circuit 108, as shown in FIG. 1c. The read channel integrated circuit 108 processes the waveform and produces data-representing signals having digital waveforms 110, as shown in FIG. 1d. The same integrated circuit 108 is also used during data-writing processes to transform user data in digital form to analog waveforms that are then recorded on a disk 102 via the associated magnetic transducer.
FIGS. 2 and 3 illustrate typical flow of data and signals during read and write operations. During the write operation shown in FIG. 3, the user data is first encoded using a modulation code encoder 300. The encoded data is then supplied to a waveform generator 302. During the read process, shown in FIG. 2, the data is first passed through the analog front end 204 and is then supplied to analog-to-digital converter 202. The digitized signal is then supplied to a digital front end 200 which includes digital equalization and a variety of algorithms facilitating gain and timing tracking. After passing through the digital front end, digital samples are supplied to Viterbi algorithm 206 where the user data is extracted from the input signal. The output of Viterbi algorithm, while mostly correct, typically contains a number of errors, and a post-processor 208 is therefore used to reduce the rate at which the errors occur. Then, the data is supplied to the modulation code decoder 210.
In conventional systems, the post-processor uses parity bits to check for error events. For example, given a word containing 33 bits b33,b32, . . . ,b2,b1, bit b34 is added such that:
b34+b33+b32+ . . . +b2+b1=0xe2x80x83xe2x80x83Eqn. (1)
where + stands for xe2x80x9cexclusive-orxe2x80x9d operation. The codeword b34, b33, b32, . . . , b2, b1, is then recorded on the media. If, during the read process, Viterbi algorithm makes an error, for example, in 32nd bit, producing {overscore (b)}32 instead of b32 (here {overscore (0)}=1, {overscore (1)}=0), then the control sum Eqn. (1) becomes equal to 1 instead of 0 which indicates that there is an error somewhere in the block of 34 bits. Post-processor uses this information to correct the error. Post-processor will also detect other error events, such as when three nearby bits are wrong, e.g. Viterbi outputs {overscore (b)}32,{overscore (b)}31,{overscore (b)}30 instead of b32,b31, b30.
In accordance with the present invention, a post-processor is formed and operated based on a cyclic code rather than on a parity code. The invention can be further understood with the following brief mathematical description of cyclic codes.
Every cyclic code is based on a generator polynomial g(x) with binary coefficients:
g(x)=g0+g1x+g2x2+ . . . +gmxmxe2x80x83xe2x80x83Eqn. (2)
When n-m user bits bm,bm+1, . . . , bnxe2x88x922,bnxe2x88x921 are sent to the cyclic code encoder, m extra bits b0,b1, . . . ,bmxe2x88x921 are appended at the end of the codeword. The overall code rate is hence (nxe2x88x92m)/n. During the encode process a division with remainder is preformed as follows. The input data bits can be thought of as a polynomial
binput(x)=bmxm+bm+1xm+1+ . . . bnxe2x88x922xnxe2x88x922+bnxe2x88x921xnxe2x88x921xe2x80x83xe2x80x83Eqn. (3)
of degree n""11. Dividing the polynomial binput(x) by g(x) yields a remainder r(x):
binput(x)=a(x)g(x)+r(x)xe2x80x83xe2x80x83Eqn. (4)
Here the division is performed modulo 2. Such division with remainder is commonly used in codes and further details can be found in the literature. The remainder r(x) is a polynomial of degree mxe2x88x921:
r(x)=r0+r1x+ . . . +rmxe2x88x921xmxe2x88x921xe2x80x83xe2x80x83Eqn. (5)
Then, setting:
bj={overscore (r)}j for j=0, 1, . . . , mxe2x88x921xe2x80x83xe2x80x83Eqn. (6)
The result of this encoding is that the output data word b0,b1, . . . ,bnxe2x88x921, viewed as a polynomial
b(x)=b0+b1x+ . . . +bnxe2x88x921xnxe2x88x921xe2x80x83xe2x80x83Eqn. (7)
is divisible by generator polynomial g(x) without remainder. Hence during the error detection process, division is performed with remainder on every n-bit codeword coming out from the Viterbi algorithm and if a remainder is not equal to zero, the post-processor is activated to correct the error.
Cyclic codes are the codes which employ a generator polynomial g(x), and which in addition satisfy the requirement that polynomial xn+1 is divisible by g(x) without remainder. If this requirement is satisfied then the resulting code enjoys the so-called cyclic shift property, namely that if b0,b1,b2, . . . bnxe2x88x921 is valid codeword (i.e. corresponding polynomial is divisible by g(x) without remainder) then a cyclically shifted codeword b1,b2, . . . , bnxe2x88x921,b0 is also a valid codeword.
The reason why the cyclic property is important is because if an error event (e.g., Viterbi algorithm produces {overscore (b)}32,{overscore (b)}31,{overscore (b)}30 instead of b32,b31,b30) is detected (i.e. the remainder becomes non-zero as a result of error event) then a shifted error event (e.g. Viterbi outputs {overscore (b)}7,{overscore (b)}6,{overscore (b)}5 instead of b7,b6,b5) is detected as well, as described below in greater detail.
It should also be noted that the cyclic code redundancy bits do not necessarily have to be inserted at the end of the codeword as it was in the mathematical description above. Redundancy bits can be inserted in the middle of the codeword or can even be scattered throughout the codeword and still achieve the property that the resulting codeword polynomial Eqn. (1) is divisible by generator polynomial g(x) and the cyclic property is intact.
When the cyclic code post-processor is used, according to the present invention, the read path, for example, as shown in FIG. 2, is modified to incorporate a cyclic code post-processor as shown on FIG. 5 with a cyclic code post-processor substituted for the post processor (parity type) 208 of FIG. 2. The write path in FIG. 3 is modified to incorporate a cyclic code encoder, as shown in FIG. 6. Modulation code encoder 600 produces an output that is applied to the cyclic code encoder 602 where the cyclic redundancy bits are calculated and inserted into the codeword. The output of encoder 602 is then supplied to the waveform generator 604.